from .base import Sort
from .insertion import Insertion


class Mergation(Insertion):
    '''归并排序'''

    def __init__(self, lt=True):
        super().__init__(lt)
        self.LIMIT = 16

    def name(self):
        return "归并排序"

    def sort(self, data, low=0, hight=None):
        hight = len(data) if hight is None else hight
        self.temp_data = [0] * hight
        low = 0
        thick = 1
        while thick < hight:
            for l in range(low, hight, thick*2):
                m = l+thick
                if m > hight:
                    break
                h = l+thick*2
                h = h if h <= hight else hight
                self.merge(data, l, m, h, self.temp_data)
            thick += thick

    def merge(self, data, low, middle, hight, temp_data):
        if hight - low < self.LIMIT:
            Insertion.sort(self, data, low, hight)
        else:
            l = low
            m = middle
            for i in range(low, hight):
                if l >= middle:
                    temp_data[i] = data[m]
                    m += 1
                elif m >= hight:
                    temp_data[i] = data[l]
                    l += 1
                elif self.compare(data[m], data[l]):
                    temp_data[i] = data[m]
                    m += 1
                else:
                    temp_data[i] = data[l]
                    l += 1
            for i in range(low, hight):
                data[i] = temp_data[i]
